
/*
 *  Copyright (C) 2010 Martin Haulrich <mwh.isv@cbs.dk> and Matthias Buch-Kromann <mbk.isv@cbs.dk>
 *
 *  This file is part of the IncrementalParser package.
 *
 *  The IncrementalParser program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU Lesser General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU Lesser General Public License for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
package org.osdtsystem.incparser.featureextraction;

import org.osdtsystem.incparser.features.FeatureAggregator;
import org.osdtsystem.incparser.features.FeatureHandler;
import org.osdtsystem.incparser.graphs.Graph;
import org.osdtsystem.incparser.graphs.LocalGraph;
import org.osdtsystem.incparser.graphs.ConllAdapter;

/**
 *
 * @author Martin Haulrich and Matthias Buch-Kromann
 */
public class MstFeatureExtractorUnlabelledNew extends ConllFeatureExtractor implements MstFeatureExtractorUnlabelled {
    // Feature groups
    final static int GROUP_MST_UNLABELLED = reserveFeatureGroups(1, "GROUP_MST_UNLABELLED");
    final static int GROUP_MST_LINEAR_POS = reserveFeatureGroups(26, "GROUP_MST_LINEAR_POS");
    final static int GROUP_MST_LINEAR_CPOS = reserveFeatureGroups(26, "GROUP_MST_LINEAR_CPOS");
    final static int GROUP_MST_DEPENDENCY_FORM_POSTAG = reserveFeatureGroups(28, "GROUP_MST_DEPENDENCY_FORM_POSTAG");
    final static int GROUP_MST_DEPENDENCY_FORM_CPOSTAG = reserveFeatureGroups(28, "GROUP_MST_DEPENDENCY_FORM_CPOSTAG");
    final static int GROUP_MST_DEPENDENCY_LEMMA_POSTAG = reserveFeatureGroups(28, "GROUP_MST_DEPENDENCY_LEMMA_POSTAG");
    final static int GROUP_MST_DEPENDENCY_LEMMA_CPOSTAG = reserveFeatureGroups(28, "GROUP_MST_DEPENDENCY_LEMMA_CPOSTAG");
    final static int GROUP_MST_FEATUREPAIRS_FORM = reserveFeatureGroups(28, "GROUP_MST_FEATUREPAIRS_FORM");
    final static int GROUP_MST_FEATUREPAIRS_LEMMA = reserveFeatureGroups(28, "GROUP_MST_FEATUREPAIRS_LEMMA");

    public MstFeatureExtractorUnlabelledNew(ConllAdapter adapter, FeatureHandler featureHandler) {
        super(adapter, featureHandler);
    }

    int dependencyDistance(int dep, int head) {
        int dist = Math.abs(head - dep);
        if (dist > 10) {
            dist = 10;
        } else if (dist > 5) {
            dist = 5;
        }
        return head < dep ? dist : -dist;
    }

    public void extract(FeatureAggregator aggregator, Graph graph, int node) {
         // Find head for node
        LocalGraph depGraph = graph.localGraph(node, layer);
        int headEdge = 0;
        if (depGraph.inDegree() > 0)
            headEdge = depGraph.inEdge(0);
        int head = depGraph.node(headEdge);
        extractDependency(aggregator, graph, node, head);
    }

    public void extractDependency(FeatureAggregator aggregator, Graph graph, int node, int head) {
        // Find left/right node
        int left = (head < node) ? head : node;
        int right = (head > node) ? head : node;

        // Compute dependency distance (positive if head < dep, negative otherwise)
        int distance = dependencyDistance(node, head);
        
        // Retrieve node features
        int nodeForm = adapter.form(graph, node);
        int nodeLemma = adapter.lemma(graph, node);
        int nodeCpostag = adapter.cpostag(graph, node);
        int nodePostag = adapter.postag(graph, node);
        int[] nodeFeatures = adapter.feats(graph, node);

        // Retrieve head features
        int headForm = adapter.form(graph, head);
        int headLemma = adapter.lemma(graph, head);
        int headCpostag = adapter.cpostag(graph, head);
        int headPostag = adapter.postag(graph, head);
        int[] headFeatures = adapter.feats(graph, head);

        // Extract linear features
        extractLinearFeatures(aggregator, graph, GROUP_MST_LINEAR_POS,
                left, right, distance, adapter.POSTAG);
        extractLinearFeatures(aggregator, graph, GROUP_MST_LINEAR_CPOS,
                left, right, distance, adapter.CPOSTAG);

        // Extract dependency edge features
        extractDependencyFeatures(aggregator, graph, GROUP_MST_DEPENDENCY_FORM_POSTAG,
                headForm, headPostag, nodeForm, nodePostag, distance);
        extractDependencyFeatures(aggregator, graph, GROUP_MST_DEPENDENCY_FORM_CPOSTAG,
                headForm, headCpostag, nodeForm, nodeCpostag, distance);
        extractDependencyFeatures(aggregator, graph, GROUP_MST_DEPENDENCY_LEMMA_POSTAG,
                headLemma, headPostag, nodeLemma, nodePostag, distance);
        extractDependencyFeatures(aggregator, graph, GROUP_MST_DEPENDENCY_LEMMA_CPOSTAG,
                headLemma, headCpostag, nodeLemma, nodeCpostag, distance);

        // Extract dependency features for CONLL node feature lists
        // (12 bits for distance, 10 bits for i, 10 bits for j)
        int distanceShifted = (distance + (1 << 12)) << 12;
        for (int i = headFeatures.length - 1; i >= 0; --i) {
            int headFeature = headFeatures[i];
            int packed = distanceShifted | (i << 10);
            for (int j = nodeFeatures.length - 1; j >= 0; --j) {
                int nodeFeature = nodeFeatures[j];
                extractDependencyFeatures(aggregator, graph, GROUP_MST_FEATUREPAIRS_FORM,
                        headForm, headFeature, nodeForm, nodeFeature, packed | j);
                extractDependencyFeatures(aggregator, graph, GROUP_MST_FEATUREPAIRS_LEMMA,
                        headLemma, headFeature, nodeLemma, nodeFeature, packed | j);
            }
        }
    }

    void extractLinearFeatures(FeatureAggregator aggregator, Graph graph, int featureGroup,
            int left, int right, int distance, int field) {
        // Find adjacent tokens for left/right
        int leftField = adapter.field(graph, left, field);
        int rightField = adapter.field(graph, right, field);
        int leftPrevField = left > 0 ? adapter.field(graph, left - 1, field) : FeatureHandler.START;
        int rightNextField = right < graph.nodes() - 1 ? adapter.field(graph, right + 1, field) : FeatureHandler.STOP;
        int leftNextMidField = left < right - 1 ? adapter.field(graph, left + 1, field) : FeatureHandler.MID;
        int rightPrevMidField = right > left + 1 ? adapter.field(graph, right - 1, field) : FeatureHandler.MID;

        // Add features for nodes located between left and right
        for (int i = left + 1; i < right; i++) {
            // TODO: Potential problem: Martin's code sets feature to 1, this code adds 1.
            // To test whether this change matters, try replacing node feature vectors with bit sets,
            // and compute node scores using these node feature vectors!!!
            int midField = adapter.field(graph, i, field);
            aggregator.addFeature(combine(featureGroup,
                    leftField, rightField, midField));
            aggregator.addFeature(combine(featureGroup + 1,
                    leftField, rightField, midField, distance));
        }

        // Add core POS features
        aggregator.addFeature(combine(featureGroup + 2,
                leftPrevField, leftField, rightField));
        aggregator.addFeature(combine(featureGroup + 3,
                leftPrevField, leftField, rightField, distance));
        aggregator.addFeature(combine(featureGroup + 4, 
                leftPrevField, leftField, rightField, rightNextField));
        aggregator.addFeature(combine(featureGroup + 5, 
                leftPrevField, leftField, rightField, rightNextField, distance));
        aggregator.addFeature(combine(featureGroup + 6, 
                leftPrevField, rightField, rightNextField));
        aggregator.addFeature(combine(featureGroup + 7, 
                leftPrevField, rightField, rightNextField, distance));
        aggregator.addFeature(combine(featureGroup + 8, 
                leftPrevField, leftField, rightNextField));
        aggregator.addFeature(combine(featureGroup + 9, 
                leftPrevField, leftField, rightNextField, distance));
        aggregator.addFeature(combine(featureGroup + 10, 
                leftField, rightField, rightNextField));
        aggregator.addFeature(combine(featureGroup + 11, 
                leftField, rightField, rightNextField, distance));
        aggregator.addFeature(combine(featureGroup + 12,
                leftField, leftNextMidField, rightPrevMidField));
        aggregator.addFeature(combine(featureGroup + 13,
                leftField, leftNextMidField, rightPrevMidField, distance));
        aggregator.addFeature(combine(featureGroup + 14,
                leftField, leftNextMidField, rightPrevMidField, rightField));
        aggregator.addFeature(combine(featureGroup + 15,
                leftField, leftNextMidField, rightPrevMidField, rightField, distance));
        aggregator.addFeature(combine(featureGroup + 16,
                leftField, leftNextMidField, rightField));
        aggregator.addFeature(combine(featureGroup + 17,
                leftField, leftNextMidField, rightField, distance));
        aggregator.addFeature(combine(featureGroup + 18,
                leftField, rightPrevMidField, rightField));
        aggregator.addFeature(combine(featureGroup + 19,
                leftField, rightPrevMidField, rightField, distance));
        aggregator.addFeature(combine(featureGroup + 20, 
                leftNextMidField, rightPrevMidField, rightField));
        aggregator.addFeature(combine(featureGroup + 21, 
                leftNextMidField, rightPrevMidField, rightField, distance));
        aggregator.addFeature(combine(featureGroup + 22,
                leftPrevField, leftField, rightPrevMidField, rightField));
        aggregator.addFeature(combine(featureGroup + 23,
                leftPrevField, leftField, rightPrevMidField, rightField, distance));
        aggregator.addFeature(combine(featureGroup + 24,
                leftField, leftNextMidField, rightField, rightNextField));
        aggregator.addFeature(combine(featureGroup + 25,
                leftField, leftNextMidField, rightField, rightNextField, distance));
    }

    void extractDependencyFeatures(FeatureAggregator aggregator, Graph graph,
                int featureGroup, int headType, int headTag, int nodeType, int nodeTag, int distance) {
        aggregator.addFeature(combine(featureGroup +  0, headType));
        aggregator.addFeature(combine(featureGroup +  1, headType, distance));
        aggregator.addFeature(combine(featureGroup +  2, headType, headTag));
        aggregator.addFeature(combine(featureGroup +  3, headType, headTag, distance));
        aggregator.addFeature(combine(featureGroup +  4, headType, headTag, nodeTag));
        aggregator.addFeature(combine(featureGroup +  5, headType, headTag, nodeTag, distance));
        aggregator.addFeature(combine(featureGroup +  6, headType, headTag, nodeTag, nodeType));
        aggregator.addFeature(combine(featureGroup +  7, headType, headTag, nodeTag, nodeType, distance));
        aggregator.addFeature(combine(featureGroup +  8, headType, nodeType));
        aggregator.addFeature(combine(featureGroup +  9, headType, nodeType, distance));
        aggregator.addFeature(combine(featureGroup + 10, headType, nodeTag));
        aggregator.addFeature(combine(featureGroup + 11, headType, nodeTag, distance));
        aggregator.addFeature(combine(featureGroup + 12, headTag, nodeType));
        aggregator.addFeature(combine(featureGroup + 13, headTag, nodeType, distance));
        aggregator.addFeature(combine(featureGroup + 14, headTag, nodeType, nodeTag));
        aggregator.addFeature(combine(featureGroup + 15, headTag, nodeType, nodeTag, distance));
        aggregator.addFeature(combine(featureGroup + 16, headTag, nodeTag));
        aggregator.addFeature(combine(featureGroup + 17, headTag, nodeTag, distance));
        aggregator.addFeature(combine(featureGroup + 18, nodeType, nodeTag));
        aggregator.addFeature(combine(featureGroup + 19, nodeType, nodeTag, distance));
        aggregator.addFeature(combine(featureGroup + 20, headTag));
        aggregator.addFeature(combine(featureGroup + 21, headTag, distance));
        aggregator.addFeature(combine(featureGroup + 22, nodeType));
        aggregator.addFeature(combine(featureGroup + 23, nodeType, distance));
        aggregator.addFeature(combine(featureGroup + 24, nodeTag));
        aggregator.addFeature(combine(featureGroup + 25, nodeTag, distance));
    }

    // Dependent nodes = inverse heads
    void outdateDependents(Graph graph, LocalGraph localGraph) {
        for (int edge = localGraph.outDegree() - 1; edge >= 0; --edge)
            outdate(graph, localGraph.outEdgeNode(edge));
    }

    // Adjacent nodes = inverse adjacent nodes
    void outdateAdjacentNodes(Graph graph, int node) {
        if (node > 0)
             outdate(graph, node - 1);
        if (node < graph.nodes() - 1)
             outdate(graph, node + 1);
    }

    // Dependent nodes on roof edges = inverse of mid nodes between node and head
    void outdateRoofs(Graph graph, int node) {
        // Outdate dependencies that span over this node
        for (int roof = graph.nodes() - 1; roof >= 0; --roof) {
            LocalGraph roofLocalGraph = graph.localGraph(roof, layer);
            int roofHead = roofLocalGraph.headNode();
            if ((node - roof) * (node - roofHead) < 0)
                outdate(graph, roof);
        }
    }

    public void nodeAdded(Graph graph, int node) {
        outdate(graph, node);
    }

    public void edgeAdded(Graph graph, int layer, int innode, int outnode, int type) {
        if (layer == this.layer)
            outdate(graph, innode);
    }

    public void edgeRemoved(Graph graph, int layer, int innode, int outnode, int type) {
        if (layer == this.layer)
            outdate(graph, innode);
    }

    public void edgeMoved(Graph graph, int layer, int innode, int oldoutnode, int oldtype, int newoutnode, int newtype) {
        if (layer == this.layer)
            outdate(graph, innode);
    }

    public void edgeTypeChanged(Graph graph, int layer, int innode, int outnode, int oldtype, int newtype) {
    }

    public void graphCleared(Graph graph) {
    }

    public void objectFeatureChanged(Graph graph, int node, int feature, Object value, Object oldvalue) {
        if (feature == adapter.FEATS) {
            // Outdate node
            outdate(graph, node);

            // Outdate dependents (inverse of head)
            LocalGraph localGraph = graph.localGraph(node, layer);
            outdateDependents(graph, localGraph);
        }
    }

    public void intFeatureChanged(Graph graph, int node, int feature, int value, int oldvalue) {
        if (isRegisteredIntFeature(feature)) {
            // Outdate node
            outdate(graph, node);

            // Outdate dependents (inverse of head)
            LocalGraph localGraph = graph.localGraph(node, layer);
            outdateDependents(graph, localGraph);

            // Some tags are used for adjacent nodes, or nodes in span
            if (feature == adapter.POSTAG || feature == adapter.CPOSTAG) {
                // Outdate adjacent nodes right next to node or head (inverse of adjacent nodes)
                int head = localGraph.headNode();
                outdateAdjacentNodes(graph, node);
                outdateAdjacentNodes(graph, head);

                // Outdate roof edges, ie, dependencies that span over this node
                // (inverse of mid nodes)
                outdateRoofs(graph, node);
            }
        }
    }
}
